package com.demo.java.OD551_600.OD577;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最小传输时延II(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146564367
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();  // 网格的行数
        int n = in.nextInt();  // 网格的列数

        int[][] times = new int[m][n];
        // 读取网格中的每个值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                times[i][j] = in.nextInt();
            }
        }

        // 调用 BFS 方法计算最短路径
        System.out.println(bfs(times));
    }

    public static int bfs(int[][] m) {
        int M = m.length, N = m[0].length;
        int[][] dp = new int[M][N];
        dp[0][0] = m[0][0];  // 起点的代价为 m[0][0]

        // 初始化第一列（它只可能从上面转换而来）
        for (int i = 1; i < M; ++i) {
            if (m[i][0] != m[i - 1][0]) {
                dp[i][0] = m[i][0] + dp[i - 1][0];  // 如果当前位置和上一个位置不相等，则按正常代价计算
            } else {
                dp[i][0] = m[i][0] + dp[i - 1][0] - 1;  // 如果当前位置和上一个位置相等，则减少 1
            }
        }

        // 初始化第一行（它只可能从左边转换而来）
        for (int j = 1; j < N; ++j) {
            if (m[0][j] != m[0][j - 1]) {
                dp[0][j] = m[0][j] + dp[0][j - 1];
            } else {
                dp[0][j] = m[0][j] + dp[0][j - 1] - 1;
            }
        }

        // 计算其余位置的最短路径
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j < N; ++j) {
                int up = m[i][j] + dp[i - 1][j];  // 从上面走来
                if (m[i][j] == m[i - 1][j]) {
                    up = up - 1;  // 如果和上方的值相等，则减去 1
                }

                int left = m[i][j] + dp[i][j - 1];  // 从左边走来
                if (m[i][j] == m[i][j - 1]) {
                    left = left - 1;
                }

                int tri = m[i][j] + dp[i - 1][j - 1]; // 从左上角走来
                if (m[i][j] == m[i][j - 1]) {
                    tri = tri - 1;
                }
                dp[i][j] = Math.min(left, Math.min(up, tri));  // 选择最小的路径代价
            }
        }

        // 返回右下角的最小路径代价
        return dp[M - 1][N - 1];
    }
}